#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e4 + 10, INF = 2147483647;

int n, m, s; 
vector<PII> edges[N]; 

int dist[N];
bool st[N];

void spfa(int s)
{
	for(int i = 0; i <= n; i++) dist[i] = INF;
	dist[s] = 0;
	queue<int> q;
	q.push(s);
	while(q.size())
	{
		int t = q.front(); q.pop();
		st[t] = false;
		for(auto x : edges[t])
		{
			int b = x.first, c = x.second;
			if(dist[t] + c < dist[b])
			{
				dist[b] = dist[t] + c;
				if(!st[b]) 
				{
					q.push(b);
					st[b] = true;
				}
			}	
		}	
	}		
	for(int i = 1; i <= n; i++) cout << dist[i] << " ";
}

int main()
{
	cin >> n >> m >> s;
	for(int i = 1; i <= m; i++)
	{
		int u, v, w; cin >> u >> v >> w;
		edges[u].push_back({v ,w});
	}
	
	spfa(s);
	
	return 0;
}
